/*!
 Temelia - Red-black tree samples.

 Copyright (C) 2008 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include "include/samples.h"
#include <temelia/red_black_tree.h>

static void sample1()
{
	red_black_tree_t red_black, aux;
	int **x, i, N = 100;

	PRINT("\n\n Sample 1 started \n\n");

	x = int_array_new(2 * N, 100);
	red_black = red_black_tree_new(x[0]);

	for (i = 1; i < N; i++)
	{
		PRINT("Inserez %d.\n", x[i][0]);
		aux = red_black_tree_insert(&red_black, x[i], int_compare, NULL, 1);
	}

	red_black_tree_show_indented(red_black, int_level_handler, NULL);

	PRINT("Min = %d, Max = %d\n", *(int *) red_black_tree_get_key(
					red_black_tree_get_min(red_black)),
			*(int *) red_black_tree_get_key(red_black_tree_get_max(red_black)));

	red_black_tree_show_indented(red_black, int_level_handler, NULL);

	for (i = 0; i < N; i++)
	{
		PRINT("\nSterg %d\n", x[i][0]);
		if (red_black && red_black_tree_remove(&red_black, x[i], int_compare,
				NULL, 1))
			PRINT("Nu l-am gasit ....\n");
	}

	PRINT("\n\nArborele ramas este : %p\n", red_black);
	red_black_tree_show_indented(red_black, int_level_handler, NULL);

	/*
	 * Adaug primele N numere naturale in Red-Black si apoi testez functia de cautare.
	 */
	x[0][0] = 0;
	red_black = red_black_tree_new(x[0]);

	for (i = 1; i < N; i++)
	{
		x[i][0] = i;
		red_black_tree_insert(&red_black, x[i], int_compare, NULL, 1);
	}

	PRINT("\n\nNoul arborele este :\n");
	red_black_tree_show_indented(red_black, int_level_handler, NULL);

	for (i = 0; i < 2 * N; i++)
	{
		x[i][0] = i;
		if (red_black_tree_search(red_black, x[i], int_compare, NULL) == NULL)
			PRINT("Nu am gasit %d.\n", x[i][0]);
		else
			PRINT("Am gasit %d.\n", x[i][0]);
	}

	red_black_tree_delete(red_black);

	for (i = 0; i < 2 * N; i++)
		free(x[i]);
	free(x);

	PRINT("\n\n Sample 1 ended \n\n");
}

static void sample2()
{
	int i = 0, N = 100, **x;
	red_black_tree_t red_black1, red_black2;

	PRINT("\n\n Sample 2 started \n\n");

	x = int_array_new(N, 1000);
	red_black1 = red_black_tree_new(x[0]);
	red_black2 = red_black_tree_new(x[0]);

	// Stress test.
	for (i = 0; i < N; i++)
		red_black_tree_delete_node(red_black_tree_new(NULL));

	for (i = 1; i < N; i++)
	{
		red_black_tree_insert(&red_black1, x[i], int_compare, NULL, 1);
		red_black_tree_insert(&red_black2, x[i], int_compare, NULL, 1);
	}

	PRINT("Compare = %d\n", red_black_tree_compare_trees(red_black1,
					red_black2, int_compare, NULL));
	PRINT("Empty = %d, %d\n", red_black_tree_is_empty(red_black1),
			red_black_tree_is_empty(NULL));

	for (i = 0; i < N; i++)
		free(x[i]);
	free(x);

	red_black_tree_delete(red_black1);
	red_black_tree_delete(red_black2);

	PRINT("\n\n Sample 2 ended \n\n");
}

static void sample3()
{
	red_black_tree_t red_black;
	int **x, i, N = 100;

	PRINT("\n\n Sample 3 started \n\n");

	x = int_array_new(N, 100);
	x[0][0] = 0;
	red_black = red_black_tree_new(x[0]);

	for (i = 1; i < N; i++)
	{
		x[i][0] = i;
		red_black_tree_insert(&red_black, x[i], int_compare, NULL, 1);
	}

	red_black_tree_show_indented(red_black, int_level_handler, NULL);

	PRINT("\n\nRoot key %d\n", *(int *) red_black_tree_get_key(red_black));
	PRINT("Root : parent %p, left child %p, right child %p\n",
			red_black_tree_get_parent(red_black),
			red_black_tree_get_left_child(red_black),
			red_black_tree_get_right_child(red_black));

	PRINT("Inaltimea este %d\n", red_black_tree_get_height(red_black));

	PRINT("Adancime(min) = %d, Adancime(max) = %d\n", red_black_tree_get_depth(
					red_black_tree_get_min(red_black)), red_black_tree_get_depth(
					red_black_tree_get_max(red_black)));
	PRINT("Leaf(root) = %d, Leaf(min) = %d, Leaf(max) = %d\n",
			red_black_tree_is_leaf(red_black), red_black_tree_is_leaf(
					red_black_tree_get_min(red_black)), red_black_tree_is_leaf(
					red_black_tree_get_max(red_black)));

	PRINT("Size = %d\n", red_black_tree_get_size(red_black));

	red_black_tree_delete(red_black);

	for (i = 0; i < N; i++)
		free(x[i]);
	free(x);

	PRINT("\n\n Sample 3 ended \n\n");

}

static void sample4()
{
	red_black_tree_t red_black;
	int **x, i, N = 100;

	PRINT("\n\n Sample 4 started \n\n");

	x = int_array_new(N, 100);
	red_black = red_black_tree_new(x[0]);

	for (i = 1; i < N; i++)
		red_black_tree_insert(&red_black, x[i], int_compare, NULL, 1);

	PRINT("Arborele este :\n");
	red_black_tree_show_indented(red_black, int_level_handler, NULL);

	PRINT("\nPreorder :\n");
	red_black_tree_preorder(red_black, int_handler, NULL);

	PRINT("\nInorder :\n");
	red_black_tree_inorder(red_black, int_handler, NULL);

	PRINT("\nReverse inorder :\n");
	red_black_tree_reverse_inorder(red_black, int_handler, NULL);

	PRINT("\nPostorder :\n");
	red_black_tree_postorder(red_black, int_handler, NULL);

	PRINT("\nLevel order :\n");
	red_black_tree_level_order(red_black, int_handler, NULL);

	for (i = 0; i < N; i++)
		free(x[i]);
	free(x);

	red_black_tree_delete(red_black);

	PRINT("\n\n Sample 4 ended \n\n");
}

void run_red_black_tree_samples()
{
	sample1();
	sample2();
	sample3();
	sample4();
}
